class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        def backtrack(s, left, right):
            # s: 当前构造的括号字符串
            # left: 剩余可用的左括号数量
            # right: 剩余可用的右括号数量
            if left == 0 and right == 0:
                res.append(s)
                return
            # 只要还有左括号可以用，就可以放一个左括号
            if left > 0:
                backtrack(s + '(', left - 1, right)
            # 右括号剩余数量大于左括号时，才可以放右括号
            if right > left:
                backtrack(s + ')', left, right - 1)
        # 初始时有n个左括号和n个右括号
        backtrack('', n, n)
        return res 